The present invention relates to memory-efficient coding, and more particularly to memory-efficient trellis coding.
The invention relates to an arrangement for trellis coding of input values, preferably transformed pixel data of a picture, in which a trellis is formed, with an input value being assigned to each trellis column, while a predetermined number of possible states is provided in each trellis column in which the selection of a path from at least two admitted paths from one state of a trellis column n to that state in the next trellis column n+1 to which the selected path leads is dependent on the distortion between the input value assigned to the trellis column n and quantization values which are assigned to the state in the trellis column n, the distortion being a measure of the deviation between an input value and a quantization value, and in which, by means of a path-search algorithm in the reverse direction, that path through the overall trellis is searched for which the smallest cumulated distortion is found throughout the trellis.
Trellis coding is known from the publications xe2x80x9cUniversal Trellis Coded Quantizationxe2x80x9d by James H. Kasner, Michael W. Marcellin and Bobby R. Hunt, Oct. 14, 1996 and xe2x80x9cProgressive Image Coding Using Trellis Coded Quantizationxe2x80x9d by Ali Bilgin, Philip J. Sementilli, Michael W. Marcellin, Dec. 9, 1997 and is extensively described in these publications. In accordance with these publications, a trellis is formed, i.e. a kind of lattice. In this lattice structure, an input value of the signal to be coded is assigned to each column. The trellis has as many rows as there are possible states per column in the lattice. A path is searched through the trellis, leading from the column assigned to the first input value to the last column. However, not all transitions within the trellis are admitted. Only a limited, fixed number of transitions is possible from a given admitted value in a column to the searched next admitted value in the next column. Which one of the admitted transitions is selected is made dependent on the distortion and the previously selected state which is fundamentally the difference between the input value and quantization values which in turn are assigned to the states. Thus, a path through the trellis is searched which, cumulated for all transitions in the trellis, always yields the minimal distortion from the start to the end. In this way, an end point s finally reached, i.e. a possible state in the last column of the trellis. When this point is reached, a search algorithm is used, starting from the state found for the last column, which algorithm finds a way back through the trellis, complying with the above-mentioned condition. This is possible in that, on the outward way, it is noted for each branch during the trellis coding which branch was the more favorable one. The search algorithm used for finding this path is described in both publications, in which the Viterbi algorithm is used which is known from the publication xe2x80x9cThe Viterbi Algorithmxe2x80x9d by G. D. Forney, Proc. IEEE, Vol. 61, pp. 268 to 278, May 1973.
The trellis coding may fundamentally be understood to be a one-dimensional vector quantization. As against scalar quantization, it has the advantage that also the temporal or spatial context of the input values of a sequence is taken into account in the quantization. Furthermore, a saving in the coding of the quantization values is obtained by bringing in the previous state. However, the method described above has the drawback that all values of the trellis, thus the input values, the admitted states, the distortions determined in each transition and the selected optimal transition must be stored for the entire trellis because the path-search algorithm is not used until after the trellis coding on the outward way is performed, which path-search algorithm already falls back on the stored values. Thus, a considerable memory space is required in an arrangement for performing the trellis coding.
It is an object of the invention to provide an arrangement for performing a trellis coding of this type in which the required memory space is clearly reduced.
According to the invention, this object is solved in that means for forming windows are provided, which comprise such a quantity of trellis columns assigned to consecutive input values that trellis columns of the same position in neighboring windows are remote from each other by more than a length of influence representing that maximum distance between two trellis columns for which a statistical dependence still just exists with regard to the quantization values which are selectable in the two trellis columns in the sequence of the predetermined admitted paths through the trellis, in that storage means are provided which store the data determined and required in the windows during application of the trellis coding and/or the path-search algorithm, in that a trellis coding is performed in a first window W0 of a sequence of input values, and in that in all further windows of the sequence a trellis coding is performed in each window Wn and the path-search algorithm is applied in the window Wn and subsequently in the window Wnxe2x88x921, the code words for the input values assigned to the trellis columns of the window being supplied during application of the path-search algorithm in the window Wnxe2x88x921.
The basic idea of the invention is that the trellis coding including application of the path-search algorithm is not performed via an overall sequence of pixels but is performed window by window. This presents the problem that it must be ensured when performing the trellis coding and applying its path-search algorithm that no false results are obtained owing to the division into windows, in other words, the windows may not have any influence on the results of coding the overall sequence.
According to the invention, the solution to this problem is the mode of selecting the window and the mode of employing the trellis coding including the path-search algorithm, which will be described hereinafter.
There are means for forming windows which have such a number of trellis columns, to which an input value is assigned, that columns of equal position in neighboring windows are spaced apart by more than a so-called length of influence. In other words, the length of these windows is always larger than the length of influence.
The length of influence is understood to mean the distance between two columns and thus also between the input values assigned to these columns for which, due to the properties of trellis coding, there is no statistical dependence in determining the possible states in the two columns. In trellis coding, there is fundamentally a statistical dependence in determining the possible values of consecutive pixels because only a limited number of transitions is admitted from a given state of a column n to the searched state of the subsequent column n+1. This means that not any possible state can be selected in the column n+1. The further two columns are spaced apart, the more this statistical dependence is reduced. As from a given distance between two input values and thus also between two assigned columns in the trellis, this statistical dependence is quasi no longer available because the dependence for a distance towards infinity approaches zero. The distance at which this occurs can be statistically determined by way of experiment.
Based on the use of trellis coding including the application of the path-search algorithm, the arrangement according to the invention only requires storage means which store the data determined and required in the windows during use of the trellis coding and the path-search algorithm. The required memory space is considerably reduced as compared with prior-art arrangements, because a sequence of pixels can be subdivided into a multitude of windows.
The trellis coding and application of the path-search algorithm in the windows proceeds in the following way.
At the start, a trellis coding must be performed in a first window W0 of a sequence of input values.
The following procedure applies to all subsequent windows.
In a window Wn, a trellis coding is initially performed in the trellis section associated with this window. Subsequently, the path-search algorithm is applied in this window Wn. However, code words cannot yet be supplied during use of the path-search algorithm in the window Wn, because the above-described statistical independence still does not apply to the values of this window and the length of influence has not yet been exceeded. However, this applies when employing the path-search algorithm in the previous window Wnxe2x88x921, because the length of influence for the same columns in the window Wn is exceeded for each column of this window Wnxe2x88x921 and the statistical dependence therefore no longer applies in determining the possible states. When applying the path-search algorithm in the window Wnxe2x88x921, the code words can thus be supplied. Similarly as in the prior art, the code words are supplied in dependence upon the path determined as the optimal path and the selected transitions, to which quantization values are assigned, which are supplied as code words.
Due to this selection of the window size in the trellis and the special procedure of alternately employing trellis coding on the outward way and the path-search algorithm on the way back, a considerable saving of memory space is achieved in the arrangement, because only the data of the window of the trellis must be stored.
In the alternating use of trellis coding on the outward way and the path-search algorithm on the way back, it must be ensured that the trellis coding in a window Wn starts with the same possible state which was previously determined as the last state in the same window Wn during application of the path-search algorithm. This must be ensured in order that a continuous transition occurs at the window transitions for the coding, i.e. for the values of the code words. The transitions of the window should not appear in the coding. This may be ensured that, as an admitted state, in which the trellis coding in the window Wn starts, that value is chosen which was determined by the path-search algorithm in the same window for the first column of the window.
The above-described saving of memory space may be further improved by a further embodiment of the invention as defined in claim 3. Only two memories S1 and S2 are provided which store the data of a trellis and the values determined therein.
The two memories are used in one cycle in which a trellis coding takes place in a window Wn and the path-search algorithm in the same window is applied in one memory. The path-search algorithm in the previous window is subsequently applied in the other memory. During application of the path-search algorithm in the other memory, the values are already written in the memory by the trellis values required for the subsequent trellis coding in the window Wn+1, as far as code words were supplied for given columns of the trellis. Then, the trellis coding and the path-search algorithm are performed for the window Wn+1 in the other memory. The subsequent application of the path-search algorithm in the window Wn is then again effected in the first memory, with the memory contents being already gradually replaced by the values of the next window Wn+2.
In this way, the memories are alternately used for trellis coding including the application of the path-search algorithm.
A further embodiment of the invention as defined in claim 4 uses, as path-search algorithm, the Viterbi algorithm, which can be applied in a relatively easy way.
In accordance with a further embodiment of the invention as defined in claim 5, the so-called mean-squared error is used as the above-described distortion, which error results from the square value of the difference between two values, in this case an input value and a quantization value.
In accordance with a further embodiment of the invention as defined in claim 6, the last window of a sequence is to be selected in such a way that the first and the last column of the window exceed the length of influence. This allows the use of the path-search algorithm within the last window already in the first run so that also this last window of a sequence can be coded without statistical dependence.
In accordance with a further embodiment of the invention as defined in claim 7, the input values are pixels of a still image. Before performing the trellis coding, they have been subjected to a discrete wavelet transform and the trellis coding is performed in the windows formed by this discrete wavelet transform, in which the picture data of a window represent a sequence of pixels. The statistical dependence of the pixels within this window, whose data are also denoted as sub-bands, can be very well utilized in the trellis coding.
Particularly for pixel values but also for other comparable values, for example, audio signals, a further embodiment of the invention as defined in claim 8 provides the use of the length of influence Exe2x89xa75.N in which N is the number of possible states per trellis column and thus corresponds to the number of rows in the trellis. This value is an empirical value for such signals.
These and other aspects of the invention are apparent from and will be elucidated with reference to the embodiments described hereinafter.